Вспомогательные функции

1. Базовый частотный анализ

2. Частотный метод с использованием биграмм

Поискав в Интеренете, про биграммный поиск пишут, что он просто аналогичен обычному. Тем не менее, у меня не сложилось четкого понимания, как декодировать с помощью биграмм. Очевидно, мы считаем частоту совстречаемости пар символов. Однако, дальше возникает вопрос, что делать.

Например, вот у нас в закодированной последовательности встречается такая комбинация: $$a_{t-1} a_t a_{t+1} a_{t+2}$$ Пусть мы знаем, что среди них $a_t a_{t+1}$ являются самой частой парой, и в соответствии с корпусом, мы им назначаем пару $b_t b_{t+1}$. Дальше возникает вопрос, как действовать. Например, пара $a_{t-1} a_t$ является следующей по частоте встречаемости, но ей соответсвует (по частоте в корпусе), пара $c_{t-1} c_{t}$, при чем $c_t \neq b_t$

Как поступать в таком случае?

В реализованном ниже примере используется следующий подход: мы выбираем наиболее вероятную пару из допустимых. То есть, в данном случае, мы наложим ограничение на выбор $c_{t} \equiv b_{t}$. Это позволяет однозначным образом декодировать. Недостатком является накапливание ошибки: если мы плохо декодировали самую вероятную пару, то дальше алгоритм уже не выправится.

Как видно, результат получился очень неустойчивым, и в среднем хуже, чем для униграмм.

Будем исходить из предположение, что частота встречаемости биграмм распределена нормально со средним, посчитанным по корпусу и некоторой дисперсией (которую как раз подберем по MCMC-алгоритму, смотря на количество принятых/отброшенных сэмплов). Тогда мы сможем определить вероятность встретить биграмму с такой частотой в примере по функцию нормального распределения: $$p(ab) = f(freq_{ab}, N(mu_{ab}, std))$$ где $freq_{ab}$ - частота пары $ab$ в примере, $mu_{ab}$ - частота пары $ab$ на корпусе

И в итоге можно получить вероятность данной перестановки путем произведенеия вероятностей для каждой из биграмм

3. Биграммный анализ с использованием MCMC алгоритма

Сделаем MCMC алгоритм. В качестве отдельного шага будем менять буквы в перестановке, и смотреть, как это отразится на итоговой вероятности перестановки. Выбор букв для замены будем делать равновероятным (то есть распределение для сэмплирование $q(x^{t+1}|x^t)$ - получается симметричным).

Тогда алгоритм следующий:

  1. выбираем произвольную начальную перестановку $x^0$
  2. меняем в перестановке $x^i$ две буквы и получаем $x^{i+1}$
  3. считаем $p(x^i)$, $p(x^{i+1})$ и $a(x^i, x^{i+1}) = \frac{p(x^{i+1})}{(x^i)}$
  4. если $a(x^i, x^{i+1}) >= 1$, то принимаем $x^{i+1}$ и переходим к следующему шагу (с пункта 2)
  5. если $a(x^i, x^{i+1}) < 1$, то принимаем $x^{i+1}$ с вероятностью $a(x^i, x^{i+1})$ (иначе оставляем $x^i$) и переходим к следующему шагу (с пункта 2)

Подберем значение стандартного отклонения в нормальном распределении так, чтоб число принятых было на уровне 0.5

Для более точного предсказания предлагается также сделать двухэтапную схему: сначала выходим на плато (по $p(X_{permutation})$), а затем понижаем STD, чтоб брать отбирать только наиболее вероятные перестановки. Ниже показан пример, как зависит точность предсказания от понижение std (каждую эпоху снижаем в два раза)

В целом видно, что 1000 шагов хватает для того, чтоб MCMC вышел на плато. Будем выполнять эти шаги перед началом семплирования

Пример успешного декодирования методом MCMC:

4. Распаковка "пляшущих человечков"

Первые два слова очень похожи на "если вы". Попробуем заменить их. и далее раскрутить

Еще некорые получавшиеся гипотезы: